Danych jest n liczb całkowitych dodatnich po jednej w każdym wierszu. Każda liczba jest z zakresu od 1 do 100 000.
Silnią liczby naturalnej k większej od 0 nazywamy wartość iloczynu 1·2·…·k i oznaczamy przez k!.
Przyjmujemy, że 0!=1. Zatem mamy:
0! = 1,
1! = 1,
2! = 1·2 = 2,
3! = 1·2·3 = 6,
4! = 1·2·3·4 = 24 itd.
Dowolną liczbę naturalną możemy rozbić na cyfry, a następnie policzyć sumę silni jej cyfr. Na przykład dla liczby 343 mamy 3! + 4! + 3! = 6 + 24 + 6 = 36.
Podaj, w kolejności ich występowania, wszystkie liczby, które są równe sumie silni swoich cyfr.

Wejście

Liczba n z przedziału od 1 do 500, w kolejnych n oddzielnych wierszach, znajduje się n liczb z zakresu od 1 do 100 000.

Wyjście

Liczby spełniające warunki zadania.

Przykład

            2
            145
            18
          

            145